package com.njupt.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/11 10:41
 * @Description: 77. 组合
 * @Version: 1.0
 */


public class Combine {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        backtracking(n,k,1,results,result);
        return results;
    }

    private void backtracking(int n, int k, int startIndex, List<List<Integer>> results, List<Integer> result) {
        if(result.size() == k){
            results.add(new ArrayList(result));
            return;
        }
//        for (int i = startIndex; i <=n ; i++) {
//            result.add(i);
//            backtracking(n,k,i+1,results,result);
//            result.remove(result.size()-1);
//        }
        //剪枝操作
        for (int i = startIndex; i <=n-(k- result.size())+1 ; i++) {
            result.add(i);
            backtracking(n,k,i+1,results,result);
            result.remove(result.size()-1);
        }

    }

    public static void main(String[] args) {
        Combine test = new Combine();
        List<List<Integer>> combine = test.combine(4, 2);
        System.out.println(combine);

    }
}
